import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution11UN {



    public static void main(String args[]) {
        Solution11UN s = new Solution11UN();
        System.out.println(s.maxArea(new int[]{4, 2, 3, 4}));
    }

    class Node implements Comparable<Node> {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Node o) {
            return y - o.y;
        }
    }
    public int maxArea(int[] height) {
        int n = height.length;
        Node[] nodes = new Node[n];
        Queue<Node> heap = new PriorityQueue<Node>();

        for (int i = 0; i < n; i++) {
            heap.add(new Node(i, height[i]));
        }

        int[] mp = new int[n];
        int l = 0;
        int r = n - 1;

        int maxv = 0;
        while (!heap.isEmpty()) {
            Node cn = heap.poll();
            maxv = Math.max(maxv, cn.y * Math.max(cn.x - l, r - cn.x));
            mp[cn.x] = 1;

            while (l < n && mp[l] == 1) {
                l++;
            }
            while (r >= 0 && mp[r] == 1) {
                r--;
            }
        }
        return maxv;
    }

}
